package array.others;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class GetLeastNumbers {
    public int[] getLeastNumbers_sort(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) return new int[]{};
        Arrays.sort(arr);
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) return new int[]{};
        int[] res = new int[k];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < k; i++) // 先放 k 个元素到堆中
            queue.offer(arr[i]);
        for (int i = k; i < arr.length; i++) // 与堆顶元素对比，如果小于堆顶元素，
            if (queue.peek() > arr[i]) {     // 则取出堆顶元素，放入新元素，始终保持堆内 k 个元素
                queue.poll();
                queue.offer(arr[i]);
            }

        for (int i = 0; i < k; i++) { // 将 k 个元素取出
            res[i] = queue.poll();
        }
        return res;
    }
}
